#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-12-09 10:59 上午
# @Author  : yangdy
# @File    : 2020-12-09.62.不同路径
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp = [[0 for i in range(m)] for j in range(n)]
        # for i in range(m):
        #     dp[0][i] = 1
        # for i in range(n):
        #     dp[i][0] = 1
        # for i in range(1, n):
        #     for j in range(1, m):
        #         dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # return dp[n-1][m-1]

        a = m + n - 2
        b = (m if m > n else n) - 1
        ans = 1
        for i in range(b+1, a+1):
            ans *= i
        for i in range(2, a-b+1):
            ans //= i
        return ans
